Computer-aided design (CAD) software allows a user to construct and manipulate complex three-dimensional (3D) models. A number of different modeling techniques can be used to create a 3D model. These techniques include solid modeling, wire-frame modeling, and surface modeling. Solid modeling techniques provide for topological 3D models, where the 3D model is a collection of interconnected topological entities (e.g., vertices, edges, and faces). The topological entities have corresponding supporting geometrical entities (e.g., points, trimmed curves, and trimmed surfaces). The trimmed surfaces correspond to the topological faces bounded by the edges. Wire-frame modeling techniques, on the other hand, can be used to represent a model as a collection of simple 3D lines, whereas surface modeling can be used to represent a model as a collection of exterior surfaces. CAD modeling using solid modeling techniques is widely used for industrial design and other applications requiring high-quality rendering.
A solid model is generally represented by a boundary representation (B-rep), which consists of trimmed parametric surfaces with inter-references that maintain the topology of the model. For example, an edge shared by neighboring faces will have references (sometimes called half-edges or edge-uses) to both faces.
Referring now to FIG. 1, an illustration of a B-rep topological structure of a cube 100 is shown. A half-edge e11 typically stores references to the associated face f1 of e11, the next half-edge e12 of e11, and the opposite half-edge e21 of e11. FIG. 1 illustrates that given half-edge e11, the neighboring face f2 of e11 can be identified by taking the face of the opposite half-edge e21 of e11.
A design engineer is a typical user of a 3D CAD system. The design engineer designs physical and aesthetic aspects of 3D models, and is skilled in 3D modeling techniques. The design engineer creates parts and may assemble the parts into one or more subassemblies and assemblies. During the design process, a high quality rendering of the 3D model is often desired to present the model as a real-world object.
Traditional rendering methods preprocess a model into a tessellation stored in a computer-processing unit (CPU) memory and use the tessellation for rendering. As graphics processing units (GPUs) became common components of CAD systems, interactively rendering solid models involved tessellating the models using a CPU and then transmitting the tessellation to a GPU for further processing.
The trimming of surface patches may complicate the tessellation due to fine-grained sampling along the trimming loops, which is necessary to obtain an acceptable quality of the tessellation along the trimming loops. This process is time consuming and the tessellations have significant memory requirements. For example, empirical evidence has shown that tessellated model representations generally require an order of magnitude more memory than boundary representations. Moreover, the advent of client graphics applications (e.g., in the context of cloud computing) begs for the reduction of the size of the models transmitted over the Internet.
The desire to reduce the size of a transmitted model motivated on-the-fly tessellation approaches of trimmed parametric surfaces. M. Guthe, J. Meseth, and R. Klein; Fast and memory efficient view-dependent trimmed NURBS rendering; Pacific Conference on Computer Graphics and Applications, p. 204 (2002) discusses an approach implemented on a CPU. Whereas, M. Guthe, Á. Balázs., and R. Klein; GPU-based trimming and tessellation of NURBS and T-Spline surfaces; ACM Trans. Graph. 24, 3, o. 1016 (2005) and A. Krishnamuthy, R. Khardekar, and S. McMains; Direct evaluation of NURBS curves and surfaces on the GPU; ACM Symposium on Solid and Physical Modeling, ACM, p. 329 (2007) describe approaches that utilize a GPU.
Guthe et al. (2005) described tessellating trimmed non-rational bspline (NURBS) patches by subdividing patches into rational bi-cubic Bézier patches, which are passed as textures to a GPU and evaluated directly. Trimming is performed using a trimming texture, which is generated using a method implemented on a GPU. The trim texture is computed by rendering a polygonal approximation of each trim loop in the uv-domain of a surface. The trimming texture is then used as a mask to identify pixels that are outside the face boundary (either outside the outer loop or inside a hole).
While tessellation on the GPU may not require preprocessing and storing the control meshes in CPU memory, and does reduce the amount of data transmitted over the communication network, the surfaces are still approximated by tessellation techniques. Furthermore and in general, when a user zooms into a model, the tessellation must be updated to reach a finer approximation.
As GPU technology becomes more advanced, rendering of models directly on the GPU becomes not only of higher quality, but also competitive in terms of computation speed. Methods have been described that directly render solid models and trimmed surfaces thereof directly on a GPU without a tessellation preprocess, and generally render the models when needed. (For example of the later, see Krishnamuthy et al.)
Rendering a solid model directly on the GPU without tessellating the model has advantages, which by way of non-limiting example include pixel-level rendering quality, less memory requirements, and less preprocessing requirements. Yet, one of the main problems with existing solutions for rendering solid models directly on the GPU without first creating a tessellation is the appearance of crack/gap artifacts between faces due to the approximations of trimming curves. These undesirable artifacts prevent or have a limiting effect on the usage of direct GPU rendering in CAD systems.
GPU ray casting methods are also utilized for rendering of surfaces. Such methods include rendering implicit algebraic surfaces (see C. T. Loop, and J. Blinn; Real-time GPU rendering of piecewise algebraic surfaces; ACM Trans. Graph. 25, 3, 664 (2006)) and constructive solid geometry (CSG) primitives (see F. Romeiro, L. Velho, L., and L. H. De Figueiredo; Scalable GPU rendering of csg models; Computers & Graphics 32, 5, p. 526 (2008). These methods render directly in terms of the surface polynomial representations, as opposed to a set of approximating triangles. The advantages are high-quality results compared to rendering tessellations and reduced memory usage.
Other ray casting techniques have been proposed to render parametric/trimmed surfaces directly on the GPU, such as H. F. Pabst, J. Springer, A. Schollmeyer, R. Lenhardt, C. Lessig, and B. Froehlich; Ray casting of trimmed NURBS surfaces on the GPU; Interactive Ray Tracing 2006, IEEE Symposium; p. 151 (2006), and A. Schollmeyer and B. Fröhlich; Direct trimming of NURBS surfaces on the GPU; ACM Trans. Graph. 28 (July), 47:1; (2009). These techniques use fragment shaders (also referred to as pixel shaders), to compute the intersection, or lack thereof, of a ray with a trimmed parametric surface. Such techniques enable rendering of trimmed surfaces up to pixel-level resolution seamlessly.
Ray casting of trimmed parametric surfaces, however, present further difficulties since the polynomials involved may be of higher degree, requiring numerical root extraction, and for the trimming of the surfaces, a point classification algorithm. Pabst et al. presented a GPU-based non-uniform rational b-spline (NURBS) ray casting implementation using a bi-variate Newton iteration to solve the ray-patch intersection problem. In order to achieve convergence to the root, Pabst et al. subdivide the surface into sub-patches in a preprocessing step and compute the convex hull of each sub-patch. The convex hull is then used as a bounding volume for rendering, and utilized to find a good initial value for the numeric iteration.
The trimming of the surfaces may present a problem for both tessellation and ray casting approaches. The basic problem is to classify whether a given point is inside a given face, in which case the point should be rendered, or outside the given face, in which case the point should be discarded. As previously discussed, a trimming texture can be used. Such a texture is a simple binary texture that stores, for example, a black pixel for outside and a white pixel for inside a given face. The fragment shader then checks whether the texture value corresponding to the pixel is black and if so performs no further operation using the pixel. The problem with this method is that the method introduces pixelization artifacts.
FIGS. 2a and 2b illustrate pixelization artifacts due to trimming texture decimation on a model of a duck with trimming loops around the eyes of the duck. FIG. 2a shows a full view of the duck model, whereas, FIG. 2b shows a close up view of the duck's eye. The texture is basically a pixelization of the uv-domain, and therefore, the mapping of the uv-domain of the surface to 3D space can produce noticeable effects. Recomputing the trimming texture with a higher resolution has the drawback of slowing down the application and requiring more GPU memory.
A more accurate method, which overcomes the pixelization artifacts of the trimming texture, uses the trimming curves directly for point classification. Pabst et al. provide an iterative implementation of a Bézier clipping algorithm to perform the trimming directly in the fragment shader. Schollmeyer et al. improve this method by preprocessing the trimming uv-curves into monotonic segments and using an acceleration structure combined with a bisection method to quickly identify whether a point is within a trimming loop.
The results of these more accurate trimming methods are finer and smoother surface boundaries and intersections. However, as noted by Schollmeyer et al., gaps still remain along the trim curves of adjacent faces. The reason is that the trimming curves in the surface uv-domain are approximations, and as pointed out by X. Song, T. W. Sederberg, J. Zheng, R. T. Farouki, and J. Hass; Linear perturbation methods for topologically consistent representations of free-form surface intersections; Computer Aided Geometric Design 21, p. 303 (2004), representing the trimming curves exactly is a difficult task. Therefore, an inherent gap exists in the geometry between two approximations of the same curve. Á Balázs. M. Guthe, and R. Klein writing in Fat borders: Gap filling for efficient view-dependent LOD NURBS rendering; Computers and Graphics 28, 1 (February), p. 79 (2004) attempted to overcome this problem in the context of real-time tessellation rendering by adding so-called “fat borders” that fill gaps between surface patches. However, filling the gaps in this way constructs additional geometry, which may decrease performance and introduce unwanted artifacts.
One of the main problems with existing solutions for rendering solid models as trimmed surfaces on the GPU is the appearance of crack/gap artifacts between faces due to the approximations of the trimming curves. Even where the trimming was performed using a trimming curve representation and not using trim textures as in previous techniques, gaps still existed between neighboring faces of a solid model (see Schollmeyer et al.).
Thus, a drawback of current state-of-the-art techniques includes the existence of crack/gap artifacts when directly rendering a model on a GPU without first tessellating the model. These inherent cracks/gaps are introduced by the approximation of the trimming curves. A system or method that addresses this and other drawbacks would greatly enhance current state-of-the-art computerized systems by allowing the high quality rendering of a 3D model without the undesirable crack/gap artifacts.